package 回溯.排列;

import java.util.ArrayList;
import java.util.List;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/8/6 14:54
 */
public class lc60排列序列 {


    public void recuesion(int n, boolean used[], List<String> ans, StringBuilder sb) {
        if (sb.length() == n) {
            ans.add(sb.toString());
            return;
        }
        // 提前 进行剪枝 , 如果 收集的数目到达了 k ,那就说明已经足够!不用再进行搜索了!
        if(ans.size() == k){
            return ;
        }
        for (int i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }
            sb.append(i);
            used[i] = true;
            recuesion(n, used, ans, sb);
            used[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    private int k;
    public String solve(int n, int k) {
        List<String> list = new ArrayList<>();
        this.k = k;
        recuesion(n, new boolean[n + 1], list, new StringBuilder());
        return list.get(k - 1);
    }


}
